//21 Merge Two Sorted Lists
/*
给定两个增序的链表，试将其合并成一个增序的链表

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

输入：l1 = [], l2 = []
输出：[]

输入：l1 = [], l2 = [0]
输出：[0]
*/


//递归写法  递增
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
{
	//
	if (!l2)
	{
		return l1;
	}
	if (!l1)
	{
		return l2;
	}

	//对比两个链表的结点值
	if (l1->val > l2->val)
	{
		l2->next = mergeTwoLists(l1, l2->next); //l2值较小，故该节点返回l2，并比较l2->next和l1
		return l2;
	}
	else
	{
		l1->next = mergeTwoLists(l1->next, l2);
		return l1;
	}
}

//迭代写法
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
{
	ListNode *dummy = new ListNode(0), *node = dummy; // node：主操作结点
	while (l1 && l2)
	{
		if (l1->val <= l2->val)
		{
			node->next = l1;
			l1 = l1->next;
		}
		else
		{
			node->next = l2;
			l2 = l2->next;
		}
		node = node->next;
	}
	
	//传入的l1或l2其中一个为空时，直接返回
	node->next = l1 ? l1 : l2;
	return dummy->next; //返回dummy结点的下一个，因为该链表头节点为0
}